#include <map>
#include <list>
using namespace std;

class LRUCache{
    int capacity;
    typedef list<pair<int,int> > list_type;
    typedef map<int, list_type::iterator> map_type;
    map_type m;
    list_type l;
public:
    LRUCache(int capacity) {
        this->capacity=capacity;
        m.clear();
        l.clear();
    }

    int get(int key) {
        map_type::iterator it=m.find(key);
        if (it==m.end()) return -1;
        list_type::iterator it2=it->second;
        int ret=it2->second;
        m.erase(it);
        l.erase(it2);
        l.push_front(make_pair(it2->first, it2->second));
        m.insert(make_pair(it->first, l.begin()));
        return ret;
    }

    void set(int key, int value) {
        map_type::iterator it=m.find(key);
        if (it!=m.end()){
            m.erase(it);
            l.erase(it->second);
        }
        l.push_front(make_pair(key,value));
        m.insert(make_pair(key, l.begin()));
        if (m.size()>capacity) {
            m.erase(l.back().first);
            l.pop_back();
        }
    }
};

